/*
==================================================================
* 版权所有 © 2025 CaryXiong
* Copyright (C) 2025 CaryXiong(a1816101108@outlook.com)
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
===================================================================
*/




#include <iostream>
using namespace std;


template<class DataType>
struct Node
{
    DataType data;
    Node<DataType> *next;
};

template<class DataType>
class LinkList{
    public:
        LinkList();
        LinkList(DataType a[], int n);
        int Length();
        DataType Get(int i);
        int Locate(DataType x);
        void Insert(int i, DataType x);
        DataType Delete(int i);
        bool Empty();
        void PrintList();

        void Append(DataType x);
        DataType FindMax();
        DataType FindMin();
        DataType Sum();
        DataType Average();
        DataType Delete2(int i);
        bool ifOrder();
        DataType Delete3(int i);
        int Insert2(DataType x);
        int Delete4();
        int Delete5(DataType mink1, DataType maxk2);
    
    private:
        // 单链表的头指针
        Node<DataType> *first;
};


template<class DataType>
LinkList<DataType> :: LinkList(){
    // 生成头节点
    first = new Node<DataType>;
    // 头节点指针域置空
    first -> next = nullptr;
}

/*头插法*/

/*
template<class DataType>
LinkList<DataType> :: LinkList(DataType a[], int n){
    // 初始化空链表
    first = new Node<DataType>;
    first->next = nullptr;

    for(int i=0; i<n; i++){
        Node<DataType> *s;

        s = new Node<DataType>;
        s->data = a[i];

        s->next = first->next;
        first->next = s;
    }
}
*/


/*尾插法*/
template<class DataType>
LinkList<DataType> :: LinkList(DataType a[], int n){
    first = new Node<DataType>;
    first->next = nullptr;

    // 定义尾指针
    Node<DataType> *r = first;

    for(int i=0; i<n; i++){
        Node<DataType> *s;
        s = new Node<DataType>;
        s->data = a[i];
        s->next = nullptr;

        r->next = s;
        r = s;
    }
}

template<class DataType>
int LinkList<DataType> :: Length(){
    int sum = 0;
    Node<DataType> *p = first;

    while(p->next != nullptr){
        sum++;
        p = p->next;
    }
    return sum;
}

template<class DataType>
DataType LinkList<DataType> :: Get(int i){
    if(i > Length()) throw "超出范围";

    Node<DataType> *p = first;
    for(int j=1; j<=i; j++) p = p->next;
    return p->data;
}

template<class DataType>
int LinkList<DataType> :: Locate(DataType x){
    Node<DataType> *p = first;
    int pos = 0;
    while(p->next != nullptr){
        p = p->next;
        pos ++;
        if(p->data == x) return pos;
    }
    throw "找不到该元素";
}

template<class DataType>
void LinkList<DataType> :: Insert(int i, DataType x){
    Node<DataType> *s, *p=first;
    s = new Node<DataType>;

    // 获取第i-1个元素的指针
    for(int j=1; j<=i-1; j++) p = p->next;

    s->data = x;
    s->next = p->next;
    p->next = s;
}

template<class DataType>
DataType LinkList<DataType> :: Delete(int i){
    if(i > Length()) throw "超出范围";
    Node<DataType> *p = first, *s;
    DataType value;
    // 获取第i-1个元素的指针
    for(int j=1; j<=i-1; j++) p = p->next;
    s = p->next->next;
    value = p->next->data;
    delete p->next;
    p->next = s;
    return value;
}

template<class DataType>
bool LinkList<DataType> :: Empty(){
    Node<DataType> *p = first;
    if(p->next == nullptr) return true;
    else return false;
}

// 新的元素插入在单链表的尾部
template<class DataType>
void LinkList<DataType> :: Append(DataType x){
    Node<DataType> *s, *p=first;
    s = new Node<DataType>;

    s->data = x;
    s->next = nullptr;

    while(p->next != nullptr) p = p->next;
    p->next = s;
}

template<class DataType>
void LinkList<DataType> :: PrintList(){
    Node<DataType> *p = first->next;

    while(p != nullptr){
        cout << p->data << '\t';
        p = p->next;
    }
    cout << '\n';
}

template<class DataType>
DataType LinkList<DataType> :: FindMax(){
    int location = 1, p_location = 0;
    Node<DataType> *p = first->next;
    DataType value = p->data;

    while(p != nullptr){
        p_location++;
        if(p->data > value){
            value = p->data;
            location = p_location;
        }
        p = p->next;
    }
    // cout << "最大值下标 : " << location << endl;

    return value;
}

template<class DataType>
DataType LinkList<DataType> :: FindMin(){
    int location = 1, p_location = 0;
    Node<DataType> *p = first->next;
    DataType value = p->data;

    while(p != nullptr){
        p_location++;
        if(p->data < value){
            value = p->data;
            location = p_location;
        }
        p = p->next;
    }
    // cout << "最小值下标 : " << location << endl;

    return value;
}

template<class DataType>
DataType LinkList<DataType> :: Sum(){
    Node<DataType> *p = first->next;
    DataType value = 0;

    while(p != nullptr){
        value += p->data;
        p = p->next;
    }

    return value;
}

template<class DataType>
DataType LinkList<DataType> :: Average(){
    DataType value = Sum()/Length();
    return value;
}

template<class DataType>
DataType LinkList<DataType> :: Delete2(int i){
    Node<DataType> *p = first, *s;
    DataType value;
    for(int j=0; j<i-1; j++){
        if(p->next == nullptr) throw "超出范围";
        p = p->next;
    }
    if(p->next != nullptr){
        if(p->next->next != nullptr){
            s = p->next->next->next;
            value = p->next->next->data;
            delete p->next->next;
            delete p->next;
            p->next = s;
            return value;
        }
        else{throw "要删除的元素不存在";}
    }
    else{throw "要删除的元素不存在";}
    return 0;
}

template<class DataType>
bool LinkList<DataType> :: ifOrder(){
    Node<DataType> *p = first;
    int state;

    if(p->next == nullptr) throw "表空 无法判断是否有序";
    else{
        // 单减
        if(p->next->data > p->next->next->data) state = 0;
        // 单增
        else if(p->next->data < p->next->next->data) state = 1;
        else return false;
        p = p->next;
        while(p->next != nullptr){
            if(state==0 && p->data <= p->next->data) return false;
            else if(state==1 && p->data >= p->next->data) return false;
            else p = p->next;
        }
        return true;
    }
}

template<class DataType>
DataType LinkList<DataType> :: Delete3(int i){
    Node<DataType> *p = first, *s;
    DataType value;

    for(int j=0; j<i-1; j++){
        if(p->next == nullptr) throw "超出范围";
        p = p->next;
    }
    if(p->next == nullptr) throw "超出范围";
    else if(p->next!=nullptr && p->next->next==nullptr){
        value = p->next->data;
        delete p->next;
        p->next = nullptr;
        return value;
    }
    else if(p->next!=nullptr && p->next->next!=nullptr){
        value = p->next->next->data;
        s = p->next->next->next;
        delete p->next->next;
        delete p->next;
        p->next = s;
        return value;
    }
    return 0;
}

template<class DataType>
int LinkList<DataType> :: Insert2(DataType x){
    Node<DataType> *p = first, *s;
    int position = 2;
    if(!ifOrder()) throw "非严格单调数据组";
    else{
        if(p->next->data < p->next->next->data){
            while(p->next!=nullptr && p->next->data < x){
                p = p->next;
                position++;
            }
            s = new Node<DataType>;
            s->data = x;
            s->next = p->next;
            p->next = s;
        }else{
            while(p->next!=nullptr && p->next->data > x){
                p = p->next;
                position++;
            }
            s = new Node<DataType>;
            s->data = x;
            s->next = p->next;
            p->next = s;
        }
        return position;
    }
}

template<class DataType>
int LinkList<DataType> :: Delete4(){
    Node<DataType> *p = first->next, *s;
    int count = 0;
    while(p->next != nullptr){
        if(p->data == p->next->data){
            s = p->next->next;
            delete p->next;
            p->next = s;
            count ++;
        }else p = p->next;
    }
    return count;
}

template<class DataType>
int LinkList<DataType> :: Delete5(DataType mink1, DataType maxk2){
    Node<DataType> *p = first, *s;
    int count = 0;
    while(p->next != nullptr){
        if(p->next->data<maxk2 && p->next->data>mink1){
            s = p->next->next;
            delete p->next;
            p->next = s;
            count ++;
        }else p = p->next;
    }
    return count;
}




int main(){
    int a[5] = {20,21,22,23,24};
    
    LinkList<int> L(a,5);
    cout << "单链表长度：" << L.Length() << endl;
    cout << "获取第3个元素：" << L.Get(3) << endl;
    cout << "元素21位于第 " << L.Locate(21) << " 个位置" << endl;
    cout << "向第3个位置插入数据2233：";
    L.Insert(3,2233);
    L.PrintList();
    cout << "删除第3个元素：" << L.Delete(3) << endl;
    cout << "当前链表内容："; L.PrintList();
    cout << "判断链表是否为空：";
    if(L.Empty()) cout << "EMPTY" << endl;
    else cout << "NOT EMPTY" << endl;

    cout << "查找链表的最大元素：" << L.FindMax() << endl;
    cout << "查找链表的最小元素：" << L.FindMin() << endl;
    cout << "链表元素求和：" << L.Sum() << endl;
    cout << "链表元素求均值：" << L.Average() << endl;
    cout << "删除第3个元素和第4个元素（若有）：" << L.Delete2(3) << endl;
    cout << "当前链表内容："; L.PrintList();
    cout << "链表是否有序：";
    if(L.ifOrder()) cout << "ORDER" << endl;
    else cout << "NOT ORDER" << endl;
    cout << "保持有序状态插入数据23：插入位置" << L.Insert2(23) << endl;
    cout << "当前链表内容："; L.PrintList();

    cout << endl << endl;

    int b[5] = {1,1,1,2,2};
    LinkList<int> L2(b,5);

    cout << "当前链表内容："; L2.PrintList();
    cout << "删除多余节点：" << L2.Delete4() << "个" << endl;
    cout << "当前链表内容："; L2.PrintList();

    cout << endl << endl;

    int c[5] = {1,2,3,4,5};
    LinkList<int> L3(c,5);

    cout << "当前链表内容："; L3.PrintList();
    cout << "删除数据值在1-4的元素（不包括边界）" << L3.Delete5(1,4) << "个" << endl;
    cout << "当前链表内容："; L3.PrintList();

    int m;
    cin >> m;
}